/*
	gen_book.cc	Open Book Generator
	Copyright (c) 2001, 2002, 2003, 2004, 2005 Kriang Lerdsuwanakij
	email:		lerdsuwa@users.sourceforge.net

	This program is free software; you can redistribute it and/or modify
	it under the terms of the GNU General Public License as published by
	the Free Software Foundation; either version 2 of the License, or
	(at your option) any later version.

	This program is distributed in the hope that it will be useful,
	but WITHOUT ANY WARRANTY; without even the implied warranty of
	MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
	GNU General Public License for more details.

	You should have received a copy of the GNU General Public License
	along with this program; if not, write to the Free Software
	Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
*/

#include "config.h"

#include <fstream>
#include <sstream>

#include <vector>

#include "book.h"
#include "hash.h"
#include "log_proc.h"
#include "binfile.h"

#include "gtstream.h"

#ifdef _
#undef _
#endif

#ifdef N_
#undef N_
#endif

#include <libintl.h>
#define _(x) gettext(x)
#define N_(x) x

//#define PRINT

// Grab version number in VERSION variable
#undef VERSION
char *
#include "scripts/version"
;

const char *prog_name = "gen_book";
const char *prog_ver = VERSION;

				// First move excluded
#define	BOOK_DEPTH	15

// Book is normalized so that the first move is C4.
// We don't use tree structure here since we must take care that
// multiple openings can lead to the same board.
struct raw_book_node;
typedef std::vector<raw_book_node *> raw_book_move_info;
typedef std::vector<raw_book_move_info> raw_book_info;

struct raw_book_next {
	int	pos;
	int	index;
	int	count;
	bool	used;		// Only used when generating binary book
	raw_book_next(int pos_ = 0, int index_ = 0, int count_ = 0)
		: pos(pos_), index(index_), count(count_) {}
};

struct raw_book_node {		// This depends on raw_book_next
	byte_board_info	board;
	std::vector<raw_book_next>	next;
	int	new_index;	// Only used when generating binary book
	bool	used;		// Only used when generating binary book

	raw_book_node() {}
};

void	swap_raw_book_next(raw_book_next &n1, raw_book_next &n2)
{
	int	tmp;
	tmp = n1.pos; n1.pos = n2.pos; n2.pos = tmp;
	tmp = n1.index; n1.index = n2.index; n2.index = tmp;
	tmp = n1.count; n1.count = n2.count; n2.count = tmp;
}

struct book_state {
	raw_book_info *book;
	std::vector<int> *hash[BOOK_DEPTH][NUM_HASH];

	book_state() {
		book = new raw_book_info;
					// Initialize hash
		for (int i = 0; i < BOOK_DEPTH; ++i)
			for (int j = 0; j < NUM_HASH; ++j)
				hash[i][j] = 0;
	}

	void free_book() {
					// Free hash
		for (int i = 0; i < BOOK_DEPTH; ++i)
			for (int j = 0; j < NUM_HASH; ++j) {
				delete hash[i][j];
				hash[i][j] = 0;
			}

		int depth = (*book).size();
		for (int i = 0; i < depth; ++i) {
			int size = (*book)[i].size();
			for (int j = 0; j < size; ++j) {
				delete (*book)[i][j];
			}
		}
		delete book;
	}

	void replace_book() {
		free_book();
		book = new raw_book_info;
	}

	~book_state() {
		free_book();
	}
};

void	init_file()
{
	binary_file_output b(get_book_data_file());
	b.write_int(0);			// Book depth
	b.write_int(12345);		// EOF Marker
}

void	store_hash(book_state &t, raw_book_node *n, int index)
{
	int	num_move = n->board.get_num_move() -1; // -1 for C4 first move
	int	hash_index = n->board.hash % (NUM_HASH-1);

				// Same hash found
	if (t.hash[num_move][hash_index]) {
				// Append
		t.hash[num_move][hash_index]->push_back(index);
	}
	else {
				// New hash
		t.hash[num_move][hash_index] = new std::vector<int>;
		t.hash[num_move][hash_index]->push_back(index);
	}
}

int	lookup_hash(book_state &t, byte_board_info *b)
{
	int	num_move = b->get_num_move() -1; // -1 for C4 first move

				// Hash information not required for
				// last move of book depth
	if (num_move >= BOOK_DEPTH)
		return 0;

	int	hash_index = b->hash % (NUM_HASH-1);

				// Same hash found
	if (t.hash[num_move][hash_index]) {
				// Search for board b
		int num_entry = t.hash[num_move][hash_index]->size();
#ifdef PRINT
std::cout << "num_entry "<< num_entry << '\n';
#endif
		for (int i = 0; i < num_entry; ++i) {
			int index = (*t.hash[num_move][hash_index])[i];
#ifdef PRINT
std::cout << "Test\n" << &((*t.book)[num_move][index]->board) << '\n' << b << '\n';
#endif
			if ((*t.book)[num_move][index]->board == *b)
				return index;
		}
	}
				// Not found

	int	num_board = (*t.book)[num_move].size();

				// Store new opening board
	raw_book_node *n = new raw_book_node;
	n->board = *b;
	(*t.book)[num_move].push_back(n);
#ifdef PRINT
std::cout << "storing id "<< num_board << '\n' << b <<'\n';
#endif

				// Store hash
	store_hash(t, n, num_board);
	return num_board;
}

// Returns next_index

int	update_info(book_state &t, int prev_index,
		    byte_board_info *b1, byte_board_info *b2, int pos)
{
	int	num_move = b1->get_num_move() -1;	// -1 for C4 first move

	int	i = prev_index;
	if (i < 0)		// -1 = need to initialize
		i = lookup_hash(t, b1);

	int	j = 0;
	if (num_move < BOOK_DEPTH)
		j = lookup_hash(t, b2);

				// Search all transition node
	int	k = 0;
	int	num_next = (*t.book)[num_move][i]->next.size();
	for ( ;  k < num_next; ++k) {
		if ((*t.book)[num_move][i]->next[k].pos == pos) {
			(*t.book)[num_move][i]->next[k].count++;

				// Sort next moves according to count
			int kk = k;
			while (kk > 0 &&
				(*t.book)[num_move][i]->next[kk].count >
				(*t.book)[num_move][i]->next[kk-1].count) {
				swap_raw_book_next((*t.book)[num_move][i]->next[kk],
					(*t.book)[num_move][i]->next[kk-1]);
				kk--;
			}
			break;
		}
	}
				// Not found, add now node
	if (k == num_next) {
		(*t.book)[num_move][i]->next.push_back(raw_book_next(pos, j, 1));
	}
	return j;
}

void	process_game(book_state &t, game_log &game)
{
	if (game.board.get_num_move())	// Ignore random opening board game
		return;

				// Extra +1 since a transition to next
				// move required
	if (game.num_move_queue < BOOK_DEPTH + 1 + 1)
		return;

				// Make sure board is correct
	if (game.board.board[D4] != WHITE)
		return;
	if (game.board.board[D5] != BLACK)
		return;
	if (game.board.board[E4] != BLACK)
		return;
	if (game.board.board[E5] != WHITE)
		return;

	byte_board_info board1(game.board);
	board1.place_piece(BLACK, C4);		// Force first move
	byte_board_info board2(board1);

	symmetry_type	sym = get_symmetry(game.move_queue[0]);
	int		prev_index = -1;	// -1 = need to initialize

	for (int i = 0; i < BOOK_DEPTH; ++i) {
		int player = game.move_queue_color[i+1];
		int pos = sym[game.move_queue[i+1]];

						// Need to pass
		if (player == game.move_queue_color[i+2])
			return;

		if (!board2.can_play(player, pos))
			throw std::runtime_error(_("invalid game moves"));
		board2.place_piece(player, pos);

		prev_index = update_info(t, prev_index, &board1, &board2, pos);

		board1 = board2;
	}
}

void	load_file(const char * /*f*/, book_state &t)
{
	binary_file_input b(get_book_data_file());
	int file_book_depth = b.read_int();

			// Trim book depth
	if (file_book_depth > BOOK_DEPTH)
		file_book_depth = BOOK_DEPTH;

	for (int i = 0; i < BOOK_DEPTH; ++i) {
		t.book->push_back(raw_book_move_info());
	}
	for (int i = 0; i < file_book_depth; ++i) {
		int num_entry = b.read_int();
		for (int j = 0; j < num_entry; ++j) {
			raw_book_node *n = new raw_book_node;
			b.read_board(n->board);

			int next_moves = b.read_int();
			for (int k = 0; k < next_moves; ++k) {
				int pos = b.read_int();
				int index = b.read_int();
				int count = b.read_int();
				n->next.push_back(raw_book_next(pos, index, count));
			}

			(*t.book)[i].push_back(n);
			store_hash(t, n, j);
		}
	}

					// Check EOF Marker
	if (b.read_int() != 12345) {
		gtstream bufstr;
		gtout(bufstr, _("cannot open file %$\n"))
			<< get_book_data_file();
		throw std::runtime_error(bufstr.str());
	}
}

//
// Remove opening moves that are rarely used.  They are either:
// 1. Used less than 5 times throughout the game database.
// 2. Used less than 1% compare to the most popular move.
//
// Idea, rarely used moves are marked with book[i][j]->used = false.
// And the "index" field of book[i][j]->next[k] is adjusted and store 
// in "new_index" accordingly.
// Rarely moves will be trimmed away in generate_file.
//

void	trim_book(book_state &t)
{
	int depth = t.book->size();

					// Clear used flag
	for (int i = 0; i < depth; ++i) {
		int num_entry = (*t.book)[i].size();
		for (int j = 0; j < num_entry; ++j) {

			if (i == 0)
					// Mark as used
					// We need to keep all the top
					// level moves since we won't
					// check them for move popularity
					// (It's always C4.)
				(*t.book)[i][j]->used = true;
			else
				(*t.book)[i][j]->used = false;

					// This is required by generate_file.
			int next_moves = (*t.book)[i][j]->next.size();
			for (int k = 0; k < next_moves; ++k) {
				(*t.book)[i][j]->next[k].used = false;
			}
		}
	}

					// Check move popularity
	for (int i = 0; i < depth; ++i) {
		int num_entry = (*t.book)[i].size();
		for (int j = 0; j < num_entry; ++j) {
			int next_moves = (*t.book)[i][j]->next.size();

					// Don't emit moves rarely used
			while (next_moves > 0
				&& ((*t.book)[i][j]->next[next_moves-1].count < 5
				    || (*t.book)[i][j]->next[next_moves-1].count*100
				       < (*t.book)[i][j]->next[0].count))
				next_moves--;

			for (int k = 0; k < next_moves; ++k) {
					// Mark as used
				(*t.book)[i][j]->next[k].used = true;
					// Last level's next index not valid
				if (i != depth-1)
					(*t.book)[i+1][(*t.book)[i][j]->next[k].index]->used = true;
			}
		}
	}

					// Calculate new_index
	for (int i = 0; i < depth; ++i) {
		int num_entry = (*t.book)[i].size();
		int cur_new_index = 0;
		for (int j = 0; j < num_entry; ++j) {
			if ((*t.book)[i][j]->used) {
				(*t.book)[i][j]->new_index = cur_new_index;
				cur_new_index++;
			}
		}
	}
}

void	generate_file(const char * /*f*/, book_state &t)
{
	trim_book(t);

	binary_file_output b(get_book_file());

	int depth = t.book->size();
	b.write_int_compress(depth);

	for (int i = 0; i < depth; ++i) {
		int num_entry = (*t.book)[i].size();
		int trim_entry = 0;
		for (int j = 0; j < num_entry; ++j) {
			if ((*t.book)[i][j]->used) {
				trim_entry++;
			}
		}

#ifdef PRINT
std::cout << "***" << i << ' ' << num_entry << '\n';
#endif
		b.write_int_compress(trim_entry);
		for (int j = 0; j < num_entry; ++j) {
			if ((*t.book)[i][j]->used) {
				int next_moves = (*t.book)[i][j]->next.size();
				unsigned char trim_next_moves = 0;

				for (int k = 0; k < next_moves; ++k) {
					if ((*t.book)[i][j]->next[k].used)
						trim_next_moves++;
				}

#ifdef PRINT
std::cout << &((*t.book)[i][j]->board) << '\n';
std::cout << next_moves << '\n';
#endif
				b.write_unsigned_char(trim_next_moves);
				for (int k = 0; k < next_moves; ++k) {
					if ((*t.book)[i][j]->next[k].used) {
						b.write_unsigned_char(
							   (*t.book)[i][j]->next[k].pos);
				// Last level's next index not valid
						if (i != depth-1)
							b.write_int_compress(
								  (*t.book)[i+1][(*t.book)[i][j]->next[k].index]->new_index);
#ifdef PRINT
std::cout << '[' << (*t.book)[i][j]->next[k].pos << ' ' 
<< (*t.book)[i][j]->next[k].index << ' ' 
<< (*t.book)[i][j]->next[k].count << "]\n";
#endif

					}
				}
			}
		}
	}

	b.write_int(12345);	// EOF Marker
}

void	store_file(const char * /*f*/, book_state &t)
{
	binary_file_output b(get_book_data_file());

	int depth = t.book->size();
	b.write_int(depth);
#ifdef PRINT
std::cout << "XXX\n";
#endif
	for (int i = 0; i < depth; ++i) {
		int num_entry = (*t.book)[i].size();
#ifdef PRINT
std::cout << "***" << i << ' ' << num_entry << '\n';
#endif
		b.write_int(num_entry);
		for (int j = 0; j < num_entry; ++j) {
			b.write_board((*t.book)[i][j]->board);
			int next_moves = (*t.book)[i][j]->next.size();
#ifdef PRINT
std::cout << &((*t.book)[i][j]->board) << '\n';
std::cout << next_moves << '\n';
#endif
			b.write_int(next_moves);
			for (int k = 0; k < next_moves; ++k) {
				b.write_int(
					  (*t.book)[i][j]->next[k].pos);
				b.write_int(
					  (*t.book)[i][j]->next[k].index);
				b.write_int(
					  (*t.book)[i][j]->next[k].count);
#ifdef PRINT
std::cout << '[' << (*t.book)[i][j]->next[k].pos << ' ' 
<< (*t.book)[i][j]->next[k].index << ' ' 
<< (*t.book)[i][j]->next[k].count << "]\n";
#endif
			}
		}
	}

	b.write_int(12345);	// EOF Marker
}

int	main_real(int argc, char *argv[])
{
	use_private_files(true);
	if (argc == 1) {
		gtout(std::cout, _("%$ %$ - Open book generator\n")) << prog_name << prog_ver;
		std::cout << _("(c) 2001, 2002, 2003, 2004, 2005 Kriang Lerdsuwanakij\n\n");
		gtout(std::cout, _("Usage:   %$ init|gen|FILES\n\n")) << prog_name;
		return 0;
	}
	else if (argc < 2)
		throw std::runtime_error(_("bad arguments"));

	book_state t;
	bool	init_book = false;
	for (int i = 1; i < argc; ++i) {
		if (strcmp(argv[i], "init") == 0) {
			init_file();
			init_book = false;	// Force reload
		}
		else if (strcmp(argv[i], "gen") == 0) {
			if (init_book == false) {
				t.replace_book();
				load_file(argv[i], t);
				init_book = true;
			}
			generate_file(argv[i], t);
		}
		else {
			if (init_book == false) {
				t.replace_book();
				load_file(argv[i], t);
				init_book = true;
			}
			process_file<game_log>(argv[i], t, false);
			store_file(argv[i], t);
		}
	}
	return 0;
}

int	main(int argc, char *argv[])
{
	try {
		return main_real(argc, argv);
	}
	catch (std::exception &e) {
		std::cout << std::flush;
		gtout(std::cerr, _("%$: %$\n")) << prog_name << e.what();
	}
	catch (const char *s) {
		std::cout << std::flush;
		gtout(std::cerr, _("%$: exception %$\n")) << prog_name << s;
	}
	catch (...) {
		std::cout << std::flush;
		gtout(std::cerr, _("%$: unknown exception\n")) << prog_name;
	}
	return 1;
}
